#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char elemtype;
typedef struct {
    unsigned int weight;
    int parent, lchild, rchild;
    elemtype data;
} huffman_node, *huffman_tree;

typedef struct {
    unsigned int weight;
    elemtype data;
} huffman_data;

typedef char *huffman_code;
typedef huffman_code *huffman_code_table;

void display_huffman_tree(huffman_tree HT, int n) {
    for (int i = 0; i < (2 * n - 1); i++) {
        printf("%2d: w:%3u  p:%2d  l:%2d  r:%2d d:%c\n", i, HT[i].weight,
               HT[i].parent, HT[i].lchild, HT[i].rchild,
               HT[i].data ? HT[i].data : '0');
    }
    printf("\n");
}

void create_huffman_tree(huffman_tree *pHT, huffman_data *arr, int n) {
    huffman_tree HT = malloc(sizeof(huffman_node) * (2 * n - 1));
    if (HT == NULL)
        exit(-1);
    memset(HT, 0, sizeof(huffman_node) * (2 * n - 1));

    for (int i = 0; i < (2 * n - 1); i++) {
        if (i < n) {
            HT[i].weight = arr[i].weight;
            HT[i].data = arr[i].data;
        }
        HT[i].parent = HT[i].lchild = HT[i].rchild = -1;
    }

    printf("init huffman_tree:\n");
    display_huffman_tree(HT, n);

    for (int i = n; i < (2 * n - 1); i++) {
        int min1 = UINT_MAX; // s1鐨勬潈鍊?鍥犱簨鍏堜笉娓呮鏉冨€艰寖鍥?
        int min2 = UINT_MAX; // s2鐨勬潈鍊?涓烘壘鏈€灏忓氨鍏堣缃渶澶?
        int min1_index = -1; // s1鐨勪綅缃?
        int min2_index = -1; // s2鐨勪綅缃?
        for (int j = 0; j < i; j++) {
            if (HT[j].parent == -1 && HT[j].weight < min1) {
                min2 = min1;
                min2_index = min1_index;
                min1 = HT[j].weight;
                min1_index = j;
            } else if (HT[j].parent == -1 && HT[j].weight < min2) {
                min2 = HT[j].weight;
                min2_index = j;
            }
        }

        HT[i].weight = min1 + min2;
        HT[i].lchild = min1_index;
        HT[i].rchild = min2_index;
        HT[min1_index].parent = HT[min2_index].parent = i;
    }

    *pHT = HT;
}

void create_huffman_code(huffman_tree HT, huffman_code_table *pHC, int n) {
    *pHC = malloc(sizeof(huffman_code) * n);
    //鍝堝か鏇兼爲鐨勯珮搴︽渶澶氫负n,璺緞闀垮害鏈€澶氫负n-1
    huffman_code code = malloc(sizeof(char) * (n - 1));

    for (int i = 0; i < n; i++) { // i涓哄彾瀛愮粨鐐圭紪鍙?
        memset(code, 0, sizeof(char) * n);
        int start = n - 1;
        int child = i;
        int father = HT[i].parent;
        while (father != -1) {
            if (HT[father].lchild == child)
                code[start--] = '0';
            else
                code[start--] = '1';
            child = father;
            father = HT[father].parent;
        }

        int len = sizeof(char) * (n - start + 1); //+1 '\0'
        (*pHC)[i] = malloc(len);
        (*pHC)[i][len] = '\0';
        strncpy((*pHC)[i], code + start + 1, len - 1);
    }
    free(code);
}

void display_huffman_code(huffman_tree HT, huffman_code_table HC, int n) {
    for (int i = 0; i < n; i++) {
        printf("%c :", HT[i].data);
        printf("%s\n", HC[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[]) {
    // huffman_data arr[] = {{7, 'a'}, {5, 'b'}, {2, 'c'}, {4, 'd'}};
    // ywm:pig 6.24-6.25

    huffman_data arr[] = {{5, 'a'}, {32, 'b'}, {18, 'c'},
                          {7, 'd'}, {25, 'e'}, {13, 'f'}};

    int arr_len = sizeof(arr) / sizeof(arr[0]);

    huffman_tree HT = NULL;

    create_huffman_tree(&HT, arr, arr_len);
    printf("create huffman_tree:\n");
    display_huffman_tree(HT, arr_len);

    huffman_code_table HC = NULL;
    create_huffman_code(HT, &HC, arr_len);

    printf("display huffman_code:\n");
    display_huffman_code(HT, HC, arr_len);

    free(HT);
    for (int i = 0; i < arr_len; i++)
        free(HC[i]);
    free(HC);

    printf("end of prog\n");

    return 0;
}
